package com.zboin.interview150;

import java.util.Arrays;

/** Normal
 * 请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
 *
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 *
 *
 * 注意：
 *
 * 一个有效的数独（部分已被填充）不一定是可解的。
 * 只需要根据以上规则，验证已经填入的数字是否有效即可。
 * 空白格用 '.' 表示。
 */
public class Course36 {

    public static void main(String[] args) {
        char[][] board = {
            {'5','3','.','.','7','.','.','.','.'}
            ,{'6','.','.','1','9','5','.','.','.'}
            ,{'.','9','8','.','.','.','.','6','.'}
            ,{'8','.','.','.','6','.','.','.','3'}
            ,{'4','.','.','8','.','3','.','.','1'}
            ,{'7','.','.','.','2','.','.','.','6'}
            ,{'.','6','.','.','.','.','2','8','.'}
            ,{'.','.','.','4','1','9','.','.','5'}
            ,{'.','.','.','.','8','.','.','7','9'}
        };

        Course36 course36 = new Course36();
        System.out.println(course36.isValidSudoku(board));
    }


    /**
     * 我的解法
     */
    public boolean isValidSudoku(char[][] board) {
        int row = board.length, col = board[0].length;
        boolean[] visited = new boolean[9];
        // row
        for (int c = 0; c < col; c++) {
            for (int r = 0; r < row; r++) {
                char ch = board[c][r];
                if (ch == '.') continue;
                int index = ch - '0' - 1;
                if (visited[index]) return false;
                visited[index] = true;
            }
            Arrays.fill(visited, false);
        }

        // column
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                char ch = board[c][r];
                if (ch == '.') continue;
                int index = ch - '0' - 1;
                if (visited[index]) return false;
                visited[index] = true;
            }
            Arrays.fill(visited, false);
        }

        // 3 x 3
        int x = 0, y = 0;
        while (x < row) {
            while (y < col) {
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        char ch = board[i + x][j + y];
                        if (ch == '.') continue;
                        int index = ch - '0' - 1;
                        if (visited[index]) return false;
                        visited[index] = true;
                    }
                }
                Arrays.fill(visited, false);
                y += 3;
            }
            x += 3;
            y = 0;
        }

        return true;
    }

    /**
     * Leetcode 上看到的大神解法
     * 主要是利用掩码位，使得一个int类型数字可以存储一行的信息：
     *  位掩码生成：
     *      int index = board[i][j] - '1'; 将字符数字（'1'-'9'）转换为索引（0-8）
     *      int shift = 1 << index; 创建一个只有第 index 位为 1 的整数（掩码）
     *  重复检查：
     *      (row & shift) != 0：检查当前行是否已存在该数字
     *      (cols[j] & shift) != 0：检查当前列是否已存在该数字
     *      (boxes[(i / 3) * 3 + j / 3] & shift) != 0：检查当前 3x3 子网格是否已存在该数字
     *  3x3 子网格定位：
     *      (i / 3) * 3 + j / 3 计算当前单元格所属的子网格索引
     *      行号 i 除以 3 确定子网格的行位置（0-2）
     *      列号 j 除以 3 确定子网格的列位置（0-2）
     *      组合得到子网格索引（0-8）
     * 更新出现情况：
     *      使用按位或操作 |= 将对应位置为 1，表示该数字已出现
     */
    public boolean isValidSudoku_nb(char[][] board) {
        int[] cols = new int[9];  // 存储每列的数字出现情况
        int[] boxes = new int[9]; // 存储每个3x3子网格的数字出现情况

        for (int i = 0; i < 9; i++) {  // 遍历每一行
            int row = 0;  // 重置当前行的数字出现情况

            for (int j = 0; j < 9; j++) {  // 遍历每一列
                if (board[i][j] != '.') {  // 跳过空白格
                    int index = board[i][j] - '1';  // 将字符转换为0-8的索引
                    int shift = 1 << index;  // 创建对应位的掩码

                    // 检查当前数字是否已在当前行、列或子网格中出现
                    if ((row & shift) != 0 || (cols[j] & shift) != 0 || (boxes[(i / 3) * 3 + j / 3] & shift) != 0) {
                        return false;  // 出现重复，数独无效
                    }

                    // 更新行、列和子网格的数字出现情况
                    row |= shift;
                    cols[j] |= shift;
                    boxes[(i / 3) * 3 + j / 3] |= shift;
                }
            }
        }

        return true;  // 所有检查通过，数独有效
    }
}
